class Solution {
    public int findRotateSteps(String ring, String key) {
        int res = 0;
        HashMap<Character, ArrayList<Integer>> location = new HashMap<>();
        ArrayList<Integer> a;
        char c;
        for (int i = 0; i < ring.length(); i++) {
            c = ring.charAt(i);
            a = location.get(c);
            if (a == null)
                a = new ArrayList<>();
            a.add(i);
            location.put(c, a);
        }

        HashMap<Integer, Integer> pre_step ; // 上一步位置，步数
        HashMap<Integer, Integer> cur_step = new HashMap<>();
        cur_step.put(0, 0);
        int min_step;

        for (char ck : key.toCharArray()) {
            res += ring.length();
            a = location.get(ck);
            pre_step = (HashMap<Integer, Integer>) cur_step.clone();
            cur_step.clear();
            for (Integer loc : a) {
                min_step = res + ring.length();
                for (Map.Entry<Integer, Integer> ps : pre_step.entrySet()) {
                    min_step = Math.min(
                            min_step,
                            1 + ps.getValue() + ring_distance(ps.getKey(), loc, ring.length())
                    );
                }
                cur_step.put(loc, min_step);
                res = Math.min(res, min_step);
            }
        }

        return res;
    }

    public static int ring_distance(int start, int end, int length){
        int res = start>end?start-end:end-start;
        return Math.min(res, length-res);
    }
}